package com.lw.leetcode.sort.c;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * 761. 特殊的二进制序列
 *
 * @author liw
 * @version 1.0
 * @date 2022/8/8 9:15
 */
public class MakeLargestSpecial {

    public static void main(String[] args) {
        MakeLargestSpecial test = new MakeLargestSpecial();

        // 11100100
//        String str = "11011000";

        // 111100100100
//        String str = "110110110000";

        // 111110000011101001100011001010
        String str = "101011001110011010001111100000";
        // () () (()) ( (()) ( () () ) )   ((((()))))



        String s = test.makeLargestSpecial(str);
        System.out.println(s);
    }

    private String s;
    private int length;
    private String[] arr = new String[50];
    private StringBuilder sb = new StringBuilder();

    public String makeLargestSpecial(String s) {
        this.s = s;
        this.length = s.length();
        find(0);
        return this.s;
    }

    private int find(int index) {
        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        int item = index;
        while (index + 1 < length) {
            if (s.charAt(index) == '1') {
                count++;
            } else {
                count--;
            }
            if (count < 0) {
                if (map.size() > 1) {
                    find(map);
                }
                return index;
            } else if (count == 0) {
                map.put(item, index);
                index++;
                item = index;
            } else if (count == 1) {
                index++;
            } else {
                count -= 2;
                int t = find(index);
                map.put(item, t);
                index = t + 1;
                item = index;
            }
        }
        if (map.size() > 1) {
            find(map);
        }
        return index;
    }

    private void find(Map<Integer, Integer> map) {
        int st = 51;
        int end = 0;
        int l = 0;
        Arrays.fill(arr, "");
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            int a = entry.getKey();
            int b = entry.getValue();
            st = Math.min(st, a);
            end = Math.max(end, b);
            arr[l++] = s.substring(a, b + 1);
        }
        Arrays.sort(arr, 0, l, (a, b) -> b.compareTo(a));
        for (int i = 0; i < l; i++) {
            sb.append(arr[i]);
        }
        this.s = s.substring(0, st) + sb.toString() + s.substring(end + 1);
        sb.setLength(0);
    }

}
